package com.zzy.algorithm.sort;


import java.util.ArrayList;
import java.util.List;

/**
 * 桶排序
 */
public class Q33_BucketSort {

    public static void main(String[] args) {
        List<Integer> array = new ArrayList<>();
        array.add(86);
        array.add(11);
        array.add(33);
        array.add(44);
        array.add(23);
        array.add(43);
        array.add(86);
        array.add(43);
        array.add(54);
        array.add(28);
        array.add(76);
        array.add(34);
        array.add(92);
        array.add(19);
        List<Integer> integers = bucketSort(array, 3);
        for(int i = 0 ; i < integers.size() ;i++){
            System.out.println(integers.get(i));
        }
    }



    private static List<Integer> bucketSort(List<Integer> list,int bucketCap){
        int min = list.get(0);
        int max = list.get(0);
        for(int x : list){
            min = Math.min(min,x);
            max = Math.max(max,x);
        }
        //确定桶的个数
        int bucketNum = (max - min) / bucketCap + 1;
        //初始化桶
        List<List<Integer>> bucketList = new ArrayList<>(bucketNum);
        for(int i = 0 ; i < bucketNum ; i++){
            bucketList.add(new ArrayList<>());
        }
        //将数据放入桶中
        for(int i = 0 ; i < list.size() ; i++){
            int num = list.get(i);
            int numInBucket = num - min;
            bucketList.get(numInBucket / 2).add(num);
        }
        List<Integer> result = new ArrayList<>();
        for(int i = 0 ; i < bucketNum ; i++){
            List<Integer> singleBucket = bucketList.get(i);
            if(singleBucket.size() > 0){
                if(bucketCap == 1){
                    result.addAll(singleBucket);
                } else {
                    bucketCap--;
                    bucketSort(singleBucket,bucketCap);
                }
            }
        }
        return result;
    }







//    private static List<Integer> bucketSort(List<Integer> array,Integer bucketCap) {
//        if(array == null || array.size() < 2){
//            return array;
//        }
//        int min = array.get(0);
//        int max = array.get(0);
//        for(int i = 0 ; i < array.size(); i++){
//            if(array.get(i) > max){
//                max = array.get(i);
//            }
//            if(array.get(i) < min){
//                min = array.get(i);
//            }
//        }
//        //获得桶的数量
//        int bucketNum = (max - min) / bucketCap + 1;
//        List<List<Integer>> bucketList = new ArrayList<>(bucketNum);
//        List<Integer> result = new ArrayList<>();
//        //填充子桶
//        for(int i = 0 ; i < bucketNum ; i++){
//            bucketList.add(new ArrayList<>());
//        }
//        //将数据放入子桶
//        for(int i = 0 ; i < array.size();i++){
//            List<Integer> subBucket = bucketList.get((array.get(i) - min) / bucketCap);
//            subBucket.add(array.get(i));
//        }
//        //数据处理
//        for(int i = 0; i < bucketNum; i++){
//            List<Integer> subBucket = bucketList.get(i);
//            if(bucketCap == 1){
//                for(int j = 0 ; j < subBucket.size();j++){
//                    result.add(subBucket.get(j));
//                }
//            } else {
//                bucketCap--;
//                List<Integer> temp = bucketSort(subBucket, bucketCap);
////                if(bucketNum == 1){
////                    bucketCap--;
////                }
////                List<Integer> temp = bucketSort(subBucket, bucketCap);
////                for(int j = 0 ; j < temp.size() ; j++){
////                    result.add(temp.get(j));
////                }
//            }
//        }
//        return result;
//    }
}
